package foundation.union;

public class UnionFindNowCoder {
    private static int MAXN = 1000001;
    private static int[] father = new int[MAXN];
    private static int[] size = new int[MAXN];
    private static int[] stack = new int[MAXN];

    private static int n;

    private static void build() {
        for (int i = 0; i < n; i++) {
            father[i] = i;
            size[i] = 1;
        }
    }


    private static int find(int x) {
        int size = 0;
        while (x != father[x]) {
            stack[size++] = x;
            x = father[x];
        }
        while (size > 0) {
            father[stack[--size]] = x;
        }
        return x;
    }

    private static boolean isSameSet(int x, int y) {
        return find(x) == find(y);
    }

    private static void union(int x, int y) {
        int xRoot = find(x);
        int yRoot = find(y);
        if (xRoot != yRoot) {
            if (size[xRoot] < size[yRoot]) {
                father[xRoot] = yRoot;
                size[yRoot] += size[xRoot];
            } else {
                father[yRoot] = xRoot;
                size[xRoot] += size[yRoot];
            }
        }
    }


    public static void main(String[] args) {

    }

}
